The present invention relates to a method and apparatus which enable a verifier to conduct an en-bloc verification of individual, multiple or superimposed signatures electronically attached by a plurality of signers to one or more electronified documents in a system for decision making by circulating them to the signers. The invention also pertains to a recording medium with the verification method recorded thereon.
A typical digital signature scheme is one that utilizes the RSA cryptosystem (R. L. Rivest, et al., "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, Vol. 21, No. 2, pp.120-126 (1978)). The RSA cryptosystem is such as described below.
A signer A generates a signature key (d, N) and a verification key (e, N) so that they satisfy
N=P.times.Q PA1 e.times.d.tbd.1(mod L) PA1 where L=LCM{(P-1), (Q-1)} PA1 wherein each signer i: PA1 wherein the verifier:
Then the signer A publishes the verification key while keeping the signature key in secret. In the above, LCM{a, b} represents the least common multiple of the integers a and b, and P and Qare assumed to be two large different prime numbers. Further, a.tbd.b(mod L) represents that a-b is a multiple of L.
The RSA cryptosystem is a cryptosystem that bases its security on the difficulty in factorizing N into prime numbers when the N is large. It is difficult to compute the d-component of the secret signature key from the published verification key (N, e).
A verifier B keeps the verification key (e, N) of the signer A in combination with his identification information (ID). A trusted center may sometimes holds such verification keys in the form of a public information management directory.
A signature function D and averification function E are defined as follows: EQU D(m)=m.sup.d mod N EQU E(y)=y.sup.e mod N
It is possible to show that the following equation holds true for an integer m which satisfies 0.ltoreq.m&lt;N. EQU E(D(m))=m
where a mod N represents the remainder that results from the division of a by N.
The digital signature scheme utilizing the RSA cryptosystem is such as described below. The signer A generates f(m) from a document m using a one-way function f, then adds thereto a signature y=D(f(m)) using the secret signature function D, and sends a combination (ID, m, y) of his identification information (ID), the document m and the signature y as a signed message to the verifier B.
The verifier B retrieves the verification key information (e, N) of the signer A from the public information management file using the signer's identification information ID as the key therefor, then computes E(y)=y.sup.e mod N from the y-component of the signed message through the use of the retrieved verification key information (e, N), nd makes a check to see if E(y) matches f(m) derived from m using he one-way function f. If E(y)=f(m), then the verifier B judges that the sender is the genuine signer A and that the signed message (ID, m, y) has not been forged, because it is only the true signer A that knows the signature function D(m)=m.sup.d mod N, i.e. the aforementioned d-component.
The one-way function f mentioned herein is a function with which it is easy to calculate f(x) from x but it is difficult to obtain x from f(x). The one-way function f can be set up using a traditional high-speed encryption system, for example, a DES cryptosystem (Data Encryption Standard, Federal Information Processing Standards Publication 46, 1977). With the use of high-speed components, the time for computing the function f would substantially be negligible. The one-way function recited hereinafter is such one that can calculated a value for an x of an arbitrary data-length.
The integer N for use in the RSA cryptosystem is usually decimal 308 digits (1024 bits) or so in length. The d-component of the signature key is also about 1024-bit long. It is well-known in the art that a square-and-multiply algorithm is used to calculate the signature function D. The computation of a 308-digit integer (including a modular N calculation) needs to be performed on an average of 1536 times, imposing a heavy computational load on the signer A for signature generation.
The square-and-multiply algorithm for computing x.sup.a mod N is such as described below.
Step S1: z=1
Step S2: The following steps S2-1 and S2-2 are repeated until a numerical subscript i becomes .vertline.a.vertline.-1 from 0 (Assume that .vertline.a.vertline. represents the number of bits of a).
Step S2-1: z'=z.sup.2 mod N
Step S2-2: if a.sub.i =1, update z with z=z'x mod N (a.sub.i being a value, 0 or 1, of an i-th bit of a), and return to step S2-1.
If a.sub.i =0, return to step S2-1 without updating z.
Step S3: z is output.
(The square-and-multiply algorithm is described, for example, in Douglas R. Stinson, "CRYPTOGRAPHY, Theory and Practice," CRC, Press p127, 1995
With a view to solving the problem of increased computational load on the signer apparatus for signature generation, there have been proposed interactive proofs (typical examples of which are a Fiat-Shamir and a Schnorr scheme) (A. Fiat and A. Shamir, "How to prove yourself: practical solutions to identification and signature problems," Advances in Cryptology-Crypto 86, Springer-Verlag, pp. 186-194; C. P. Schnorr, "Efficient Identification and Signatures for smart Card," Advances in Cryptology-EUROCRYPT7 89, springer-verlag, pp. 235-251; and M. Tompa and H. Woll, "Random Self-Reducibility and Zero Knowledge Interactive Proofs of Possession of Information," Proceedings of the 28th IEEE Symposium on the Foundation of Computer Science, pp. 472-482 (1987)).
A description will be given of a digital signature by the Schnorr scheme.
A trusted center publishes two large primes p and q which bear a relation that q is a measure of p-1, and an integer g.epsilon.(Z/pZ)*={1, 2, . . . , p-1} which has an order q.
Step S1: The signer A generates a random number s.epsilon.(Z/qZ)={0, 1, 2, . . . q-1}, then computes public information I by
I=g.sup.s mod p (1)
and publishes a pair of identification information (ID) and information I.
The signer A goes through the following procedure to prove to the verifier B that the document or message m is true or genuine.
Step S2: The signer A generates a random number r.epsilon.(Z/qZ), and computes EQU X=g.sup.r mod p (2)
Step S3: The signer A computes an integer e.epsilon.(Z/qZ) by the following equation using the one-way function f. EQU e=f(X, m) (3)
Step S4: The signer A generates the signature y by EQU y=r+er mod q (4)
and sends {ID, m, X, y} as a signed message to the verifier B.
Step S5: The verifier B computes the integer e.epsilon.(Z/qZ) using the one-way function f by EQU e=f(X, m) (5)
Step S6: The verifier B makes a check to see if the following equation holds true. EQU g.sup.y.tbd.XI.sup.e (mod p) (6)
where I is public information corresponding to the identification information ID.
As is seen from the way of generating the signature y, g.sup.y.tbd.g.sup.r (g.sup.s).sup.e.tbd.XI.sup.e (mod p); hence, when Eq. (6) holds true, then the verifier B recognizes the document m as duly sent from the signer A.
In steps S2 through S4 described above, the signature of the signer could be forged if {ID, X, m, y} were sent as a signed message when the integer e.epsilon.(Z/qZ), with which e=f(X, m) would hold, could be found by calculating X.epsilon.(Z/pZ)*, which would satisfy Eq. (6), after suitably choosing the integers e.epsilon.(Z/qZ) and y.epsilon.(Z/qZ). Since the probability with which the verification equation e=f(m, X) holds true is 1/q, however, the computational complexity involved in the forgery of signature depends on the value q. In the following description the number of bits of the prime p will be represented by .vertline.p.vertline..
With the Schnorr scheme, the signature generation processing by the sender involves a multiplication (including modular p calculations) of.vertline.p.vertline.-bit integers on an average of 3/2.vertline.q.vertline. times, a single multiplication (including modular q calculations) of .vertline.q.vertline.-bit integers and a single addition (including modular q calculations) of the .vertline.q.vertline.-bit integers.
While in the above the signed message is {ID, X, m, y}, it is also possible to use e in place of X to provide {ID, e, m, y}. In this instance, a check is made to see if the relation e=f(X, m) holds, by calculating X by X=(g.sup.y)(I.sup.e).sup.-1 mod p. When .vertline.e.vertline.&lt;.vertline.X.vertline., the latter will make the message shorter.
Now, consider that a plurality of signers sign different documents on the superimposed-signature basis. A typical example of using the superimposed-signature scheme is as follows: For example, a certification authority CA guarantees the validity of the correspondence between the public identification information ID and public information I of the signer by a digital signature T=D.sub.CA (ID, I) affixed to a document (ID, I), and sends the signature T to the signer. The signer generates a signature D.sub.ID (m, T) for a pair of the document m and the signature T through the use of the secret information corresponding to the public information I, and sends the signature D.sub.ID (m, T) to the verifier, enabling him to verify the signature D.sub.ID (m, T) of the signer and the signature T of the certification authority CA.
In the superimposed-signature scheme it is important to suppress the amount of information to be processed by the signer for signature generation, suppress the amount of information to be processed by the verifier for signature verification and prevent an increase in the signature components.
With the digital signature scheme utilizing the RSA cryptosystem, respective signers i sign documents m.sub.i in a sequential order to provide information D.sub.L (m.sub.L, . . . , D.sub.2 (f(m.sub.2, D.sub.1 (f(m.sub.1)))) . . . ), thereby implementing the superimposed-signature function. In this instance, a large amount of calculation to be processed for signature generation gives rise to a problem.
With a direct application of the Schnorr scheme to the superimposed-signature scheme, it is considered possible to employ a method of adding information {ID.sub.i, X.sub.i, y.sub.i } to documents (m.sub.1, . . . , m.sub.i-1, m.sub.i) for each signer i. The X.sub.i -component is .vertline.p.vertline.-bit long and y.sub.i -component .vertline.q.vertline.-bit long. When L signers sign, information of (.vertline.p.vertline.+.vertline.q.vertline.).times.L bits will ultimately added to a message, that is, L signers' identification information ID and documents (m.sub.1, . . . , m.sub.L). In this case, too, an increase in the signature component (X-component, y-component) causes a problem.
Next, a description will be given of the multi-signature scheme in which a plurality of signers sign one document in a sequential order. With the digital signature scheme utilizing the RSA cryptosystem, it is possible to implement the multi-signature when the plurality of signers sign on a signature y of a message {ID, m, y} one after another (i.e. D.sub.L . . . D.sub.1,(f(m))). This scheme also encounters the problem of the large amount of calculation to be processed for signature generation.
With a direct application of the Schnorr scheme to the multi-signature scheme, it is considered feasible to employ a method of adding information {ID, X, y} to a message m for each signer. The X-component is .vertline.p.vertline.-bit long and y-component .vertline.q.vertline.-bit long. When L signers sign the message in a sequential order, information of (.vertline.p.vertline.+.vertline.q.vertline.).times.L bits will ultimately be added to a message (L signers' identification information ID and document m). In this instance, too, an increase in the signature component (X-component, y-component) produces a problem.
As regards the multi-signature scheme, there has been proposed a multi-signature scheme that permits reduction of each of the X- and y-components to one by accumulating the values of the X- and y-components for each signature generating process (K. Ohta and T. Okamoto, "A Digital Multi-Signature Scheme Based on the Fiat-Shamir Scheme," Advances in Cryptology-ASIACRYPT'91, springer-Verlage, pp.139-148). Since this scheme involves two rounds of circulation of a message to signers, however, the multi-signature by L signers requires (2L-1) rounds of communication; hence, an increase in the number of communications gives rise to a problem.
With the multi-signature scheme that involves two rounds of circulation of a message to signers, it is impossible to realize the superimposed-signature scheme wherein the document to be signed differs for each signer. The reason for this is that since all documents, for example, m.sub.1 and m.sub.2, must be determined in the first round of circulation, the signature to the documents (m.sub.1, m.sub.2) cannot be generated after the generation of the signature to the document m.sub.1.
There has been proposed a scheme for modifying an ElGamal signature to the multi-signature (Atsushi Shimbo, "Multisignature Schemes Based on the ElGamal Scheme, The 1994 Symposium on Cryptography and Information Security SCIS94-2C). However, this literature is silent about the superimposed use of signature. With the proposed modified scheme, it is difficult to realize the Schnorr signature with one round of circulation, and the security of any of the proposed schemes was not strictly evaluated (see Conclusion on page 9 of the literature).
In a system utilizing the digital signature scheme, the situation occasionally arises where a plurality of signatures are gathered at one place and verified. For example, electronic money is returned to its issuing institution, wherein the validity of the electronic money is verified. In such an instance, the use of an interactive proof will permit a substantial reduction of the amount of calculation to be processed for signature generation. But the amount of calculation to be processed for signature verification may sometimes increase. For example, Schnorr scheme involves multiplication of .vertline.p.vertline.-bit integers (including modular p calculations) on an average of 3/2.vertline.q.vertline. times, but in the RSA scheme, since e=3 can be achieved without impairing the security, the number of multiplications of .vertline.N.vertline.-bit integers (including modular N calculations) is only two.
Now, a description will be given of en-bloc verification of a plurality of signatures in the above-mentioned digital signature scheme.
Since the digital signature scheme utilizing the RSA cryptosystem encounters the problem of the large amount of calculation to be processed for signature generation and uses the value N.sub.i of a different modulus for each signer, it is considered impossible to verify N.sub.i and N.sub.j at one time.
When the Schnorr scheme is used without any modifications, the signer i signs a message m.sub.i by adding thereto information {ID.sub.i, X.sub.i, y.sub.i }, where the X.sub.i -component is .vertline.p.vertline. bits in length and the y.sub.i -component .vertline.q.vertline. bits in length. In the case where L signers i each sign a different document m.sub.i (where 1.ltoreq.i.ltoreq.L) and L independent verification equations are used to verify the L signatures, the amount of calculation to be processed for signature verification is L rounds of verification.
In view of the above, there has been proposed a scheme that uses the following one verification equation by accumulating the value of the y-component. EQU g.sup.y '=X.sub.1 I.sub.1.sup.e.sup..sub.L . . . X.sub.L I.sub.L.sup.e.sup..sub.L (mod p) (7)
where ##EQU1##
See, for example, Ohta and Okamoto, "Multi-Signature Schemes Using Fiat-Shamir Scheme," Spring National Convention of the Institute of Electronics, Information and Communication Engineers of Japan (1989), A-277 (1989), and Harada and Tatebayashi, "An efficient method for computing a general monomial and its application," Technical Report of Institute of Electronics, Information and Communication Engineers of Japan ISEC91-40 (1991).
With these schemes, each signer can forge other signers' signatures, giving rise to a problem in terms of security. This problem is discussed, for example, in Shimbo and Kawamura, "Consideration on computing vector addition chain and its application," Technical Report of the Institute of Electronics, Information and Communication Engineers of Japan ISEC91-59 (1991).
In the above literature there are described the signature generation, the signature verification and attacks thereto in the situation where a plurality of signers sign one document; but even if each signer signs a different document, the use of the afore-mentioned verification equation allows the direct application of the attack to the multiple signature, producing a security problem.